GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>String-Matching-Algorithmus</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">String-Matching-Algorithmus</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">In der Informatik sind String-Matching-Algorithmen eine Gruppe von <a href="Algorithmus" title="Algorithmus">Algorithmen</a>, die das Finden von Textsegmenten in einer <a href="Zeichenkette" title="Zeichenkette">Zeichenkette</a> (<a href="Englische_Sprache" title="Englische Sprache">englisch</a> string) anhand eines vorgegebenen Suchmusters beschreiben. Sie zählen somit zur Klasse der <a href="Zeichenkettenalgorithmus" title="Zeichenkettenalgorithmus">Zeichenkettenalgorithmen</a>.

Im engeren Sinne suchen diese <a href="Algorithmus" title="Algorithmus">Algorithmen</a> nach exakten Übereinstimmungen (<a href="Englische_Sprache" title="Englische Sprache">englisch</a> matches). Im weiteren Sinne sind auch Algorithmen gemeint, die ungefähre Übereinstimmungen zulassen, wobei der Begriff <a href="Unscharfe_Suche" title="Unscharfe Suche">ungefähr</a> durch ein Toleranzkriterium genau definiert sein muss.

Das Problem besteht darin, diese Aufgabe möglichst effizient zu lösen. In der Praxis ist dies bedeutsam, wenn in großen Textmengen (wie z. B. einer Wikipedia) Suchbegriffe gefunden werden sollen.

<div class="mw-heading mw-heading2"><h2 id="Exakte_Suche">Exakte Suche</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Problemstellung">Problemstellung</h3></div>

Grundsätzlich sind zwei Situationen zu unterscheiden:

<ol><li>Nach Vorgabe einer Suchmaske sollen beliebige Texte durchsucht werden.</li>

<li>Der Text ist vorgegeben, und dann sollen beliebige Suchmasken im Text gefunden werden.</li></ol>

Der zweite Fall entspricht etwa der Aufgabe, die <a href="Wikipedia" title="Wikipedia">Wikipedia</a> derart aufzubereiten, dass beliebige Suchmasken schnell und effizient aufgefunden werden. Auch <a href="Suchmaschine" title="Suchmaschine">Suchmaschinen</a> im Internet finden sich in der zweiten Situation.

Im Folgenden wird jedoch nur auf die erste Situation eingegangen.

<div class="mw-heading mw-heading3"><h3 id="Lösungsmethoden">Lösungsmethoden</h3></div>

<div class="mw-heading mw-heading4"><h4 id="Naiver_Algorithmus">Naiver Algorithmus</h4></div>

Der einfachste Algorithmus besteht darin, ein so genanntes Suchfenster von der Länge der Suchmaske über den Text zu schieben. In jeder Position der Suchmaske werden die Symbole der Maske mit denen des darunterliegenden Textes verglichen.

Wenn ein nicht übereinstimmendes Symbol gefunden wird, wird das Fenster um eine Position verschoben, und erneut ein Vergleich angestellt; wenn alle Symbole im Fenster übereinstimmen, ist die Suchmaske gefunden worden. Der Algorithmus endet, wenn der ganze Text vom Fenster abgesucht worden ist.

Dieser Algorithmus hat eine <a href="Zeitkomplexit%C3%A4t" title="Zeitkomplexität">Laufzeit</a> von der <a href="Landau-Notation" class="mw-redirect" title="Landau-Notation">Ordnung</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle {\mathcal {O}}(n\cdot m)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle {\mathcal {O}}(n\cdot m)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3e773933a5915fcef708dad5b8a0d000fe246a6c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.773ex; height:2.843ex;" alt="{\displaystyle \textstyle {\mathcal {O}}(n\cdot m)}" loading="lazy">, wenn m die Länge der Suchmaske und n die Länge des Textes ist.

Pseudocode:

<pre>Eingabe: Strings T = T1… Tn und P = P1 … Pm

Ausgabe: q die Stellen, an denen P in T auftritt

</pre>

<div class="mw-highlight mw-highlight-lang-pascal mw-content-ltr" dir="ltr"><pre> for q = 0 to n – m do

if P[1] = T[q+1] and P[2] = T[q+2] and … and P[m] = T[q+m] then

write q

</pre></div>

Überraschenderweise ist der naive Ansatz in der Praxis sehr schnell, da Fehler in natürlichsprachigen Texten nach 1 bis 2 Zeichen auftauchen. Für die englische Sprache ergibt sich eine Wahrscheinlichkeit von 1.07 Zeichen. Somit ist der naive Ansatz nahezu linear schnell.

Dies wird auch deutlich wenn man sich den ungünstigsten Fall selbst ansieht. Er lautet

<pre>Text: aaa...aab

Muster: ab

</pre>

Derartige Fälle sind in natürlich sprachlichen Texten äußerst unwahrscheinlich.

<div class="mw-heading mw-heading4"><h4 id="Endlicher_Automat">Endlicher Automat</h4></div>

Bei dem String-Matching-Algorithmus mit Hilfe von <a href="Endlicher_Automat" title="Endlicher Automat">endlichen Automaten</a> wird ein für ein Alphabet <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy"> und ein gegebenes Suchmuster der Länge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> ein Automat <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (Q,\Sigma ,\delta ,q_{0},\{q_{m}\})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (Q,\Sigma ,\delta ,q_{0},\{q_{m}\})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b9f8ee017aef628bcef4f09053f000f3158f5196.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.638ex; height:2.843ex;" alt="{\displaystyle (Q,\Sigma ,\delta ,q_{0},\{q_{m}\})}" loading="lazy"> mit Zustandsmenge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle Q=\{q_{i}\mid 0\leq i\leq m\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle Q=\{q_{i}\mid 0\leq i\leq m\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4513b18e48caabf761a4c1bd478462a5056a4d48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.238ex; height:2.843ex;" alt="{\displaystyle \textstyle Q=\{q_{i}\mid 0\leq i\leq m\}}" loading="lazy"> erstellt. Dabei stellt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle i}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b69dce609a74290821dcbd7db868b1af9c061fd4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle \textstyle i}" loading="lazy"> die Anzahl von übereinstimmenden Buchstaben an der aktuellen Stelle vom Anfang des Suchmusters an betrachtet dar. Zur Einfachheit sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle P_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle P_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/31b8c620fd51592c1bbf17483fc4c43ab15ec63d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle \textstyle P_{i}}" loading="lazy"> das <a href="Pr%C3%A4fix" title="Präfix">Präfix</a> des Suchmusters bis einschließlich des Buchstabens an der Stelle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle i}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b69dce609a74290821dcbd7db868b1af9c061fd4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle \textstyle i}" loading="lazy">. Die Übergangsfunktion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta (q_{i},a)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta (q_{i},a)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4c230ced9ef3d91471a6f94a0915891e66173a4a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.958ex; height:2.843ex;" alt="{\displaystyle \delta (q_{i},a)}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\in \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\in \Sigma }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/69a485a3b32b5e024b7b34f5e59c42e3d60337a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.749ex; height:2.176ex;" alt="{\displaystyle a\in \Sigma }" loading="lazy"> gibt nun für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq i\leq m-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq i\leq m-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ca4b2f05ce28398ed53128680921025e92b3fc4e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:14.205ex; height:2.343ex;" alt="{\displaystyle 0\leq i\leq m-1}" loading="lazy"> wieder einen Zustand <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e0d567ac2d170501680d2efa4c1d71d6a8569ef1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.947ex; height:2.343ex;" alt="{\displaystyle q_{j}}" loading="lazy"> zurück, bei dem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> die maximale Anzahl von Buchstaben darstellt, mit der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4a5da6c3564a2129f714ef11acd8ba649d18e604.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.402ex; height:2.843ex;" alt="{\displaystyle P_{j}}" loading="lazy"> ein <a href="Suffix" title="Suffix">Suffix</a> vom Wort <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{i}a}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{i}a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/62a5dc51b69f4c5d9dd577faada4dae9ab30cc33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.522ex; height:2.509ex;" alt="{\displaystyle P_{i}a}" loading="lazy"> ist. Also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta (q_{i},a)=q_{max\{j\mid P_{j}{\text{ ist Suffix von }}P_{i}a\}}}">

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

<mtext> ist Suffix von </mtext>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta (q_{i},a)=q_{max\{j\mid P_{j}{\text{ ist Suffix von }}P_{i}a\}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a1fa8aefb85012312dec1e91d91576c76f389d21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:32.508ex; height:3.343ex;" alt="{\displaystyle \delta (q_{i},a)=q_{max\{j\mid P_{j}{\text{ ist Suffix von }}P_{i}a\}}}" loading="lazy">. Ist das Suchmuster gefunden, wird im Endzustand verharrt, also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta (q_{m},a)=q_{m}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta (q_{m},a)=q_{m}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b87ce96a948fa45faf9770262d7971770b2b60c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.644ex; height:2.843ex;" alt="{\displaystyle \delta (q_{m},a)=q_{m}}" loading="lazy">.

Der Vorteil dieses Algorithmus gegenüber dem naiven Algorithmus liegt darin, dass er auch beim Finden eines nicht-passenden Zeichens das erlangte Wissen über den bereits verarbeiteten Teil der Zeichenkette nicht verwirft. Angenommen, wir suchen das Muster anax im Text ananax. Trifft der automatenbasierte Algorithmus bei der Suche auf das Zweite n in ananax, so wird er die ersten beiden Buchstaben verwerfen und beginnend mit ananax weitersuchen. Der naive Algorithmus hingegen hätte den kompletten bereits verarbeiteten Teil verworfen und hätte beginnend mit ananax einen nächsten Versuch begonnen.

Python-Implementation

<div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre>def is_suffix(suffix, word):

'''Überprüft ob das suffix ein Suffix von word ist.'''

return word.endswith(suffix)

def transition(pattern, state, event):

'''Hier wird die Übergangsfunktion berechnet.'''

for k in range(state + 1, 0, -1):

if is_suffix(pattern[:k], pattern[:state] + event):

return k

return 0

def create_matcher(alphabet, pattern):

'''Erzeugt alle Zustände und eine Übergangsfunktions-Tabelle'''

transition_table = {}

for state in range(0, len(pattern) + 1):

for event in alphabet:

transition_table[(state, event)] = \

transition(pattern, state, event)

return transition_table, len(pattern)

def match(matcher, text):

'''Gibt die gefundenen Treffer im Text mit dem Automaten der aus create_matcher

erstellt wurde.'''

transition_table, last_state = matcher

matches = []

state = 0

text_pos = 0

for text_pos in range(0, len(text)):

state = transition_table[(state, text[text_pos])]

if state == last_state:

matches.append(text_pos - last_state + 1)

return matches

def find(alphabet, pattern, text):

matcher = create_matcher(alphabet, pattern)

return match(matcher, text)

</pre></div>

<div class="mw-heading mw-heading4"><h4 id="Der_Knuth-Morris-Pratt-Algorithmus">Der Knuth-Morris-Pratt-Algorithmus</h4></div>

Der <a href="Knuth-Morris-Pratt-Algorithmus" title="Knuth-Morris-Pratt-Algorithmus">Knuth-Morris-Pratt-Algorithmus</a> baut auf dem naiven Suchalgorithmus auf. Wesentlicher Unterschied ist, dass das Vergleichsfenster nicht immer um nur eine Position weitergerückt wird, sondern eventuell um mehr als eine Position.

Dazu muss zu Anfang die Suchmaske analysiert werden, so dass bei jeder teilweisen Übereinstimmung, etwa der ersten k Symbole, bekannt ist, ob der Anfang der Suchmaske mit dem Ende der letzten übereinstimmenden Teilmaske übereinstimmt. Die Verschiebung der Suchmaske erfolgt nach der überlappenden Übereinstimmung; zusätzlicher Vorteil ist, dass die schon verglichenen Symbole nicht noch einmal verglichen werden müssen.

<div class="mw-heading mw-heading4"><h4 id="Suche_im_Suffixbaum">Suche im Suffixbaum</h4></div>

Insbesondere wenn der zu durchsuchende Text im Voraus bekannt ist, und in diesem später nach vielen unterschiedlichen Mustern gesucht werden soll, bietet sich die Konstruktion eines <a href="Suffixbaum" title="Suffixbaum">Suffixbaums</a> an. Diese Konstruktion kann in <a href="Landau-Symbole" title="Landau-Symbole"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/14f3ed5ee67068a3618a144e8b2111fe62e1415b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle \textstyle {\mathcal {O}}(n)}" loading="lazy"></a> erfolgen. Anschließend kann jedes Muster ohne erneute Vorbereitung des Texts in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle {\mathcal {O}}(m)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle {\mathcal {O}}(m)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/32b3a9961222cecce1d8188715b8ef6d6530859e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.7ex; height:2.843ex;" alt="{\displaystyle \textstyle {\mathcal {O}}(m)}" loading="lazy"> gesucht werden: Sofern es vorhanden ist, kann man von der Quelle des Suffixbaums den entsprechenden Knoten erreichen, ansonsten schlägt die Suche fehl (es ist kein entsprechender Knoten vorhanden).<a href="#cite_note-1">[1]</a>

<div class="mw-heading mw-heading3"><h3 id="Übersicht">Übersicht</h3></div>

<th>Algorithmus

</th>

<th>Vorbereitungszeit

</th>

<th><a href="Zeitkomplexit%C3%A4t" title="Zeitkomplexität">Suchzeit</a>

</th></tr>

<tr>

<td>Naiver Algorithmus

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> (keine)

</td>

<mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(\left(n-m+1\right)\cdot m\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7279d9cb0415f308206a92eac1148eba460f33cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.812ex; height:2.843ex;" alt="{\displaystyle \Theta \left(\left(n-m+1\right)\cdot m\right)}" loading="lazy">

</td></tr>

<tr>

<td><a href="Rabin-Karp-Algorithmus" title="Rabin-Karp-Algorithmus">Rabin-Karp-Algorithmus</a>

</td>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(m\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c1fac36dd016e3eb6bb57f00fae9a08a7a55d9bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.045ex; height:2.843ex;" alt="{\displaystyle \Theta \left(m\right)}" loading="lazy">

</td>

<td>average <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta \left(n+m\right)}">

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(n+m\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/548fc0ba1a2305096e270a17a66c47b106298682.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.28ex; height:2.843ex;" alt="{\displaystyle \Theta \left(n+m\right)}" loading="lazy">, worst <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta \left(n\cdot m\right)}">

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(n\cdot m\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fdc704d9de72c93d5e78ae9b401b1e3a93152147.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.119ex; height:2.843ex;" alt="{\displaystyle \Theta \left(n\cdot m\right)}" loading="lazy">

</td></tr>

<tr>

<td><a href="Endlicher_Automat" title="Endlicher Automat">Endlicher Automat</a>

</td>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(m\cdot |\Sigma |\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a4bd499ca80583c9f3d7e0fd04b42b528ac9a590.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.738ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}\left(m\cdot |\Sigma |\right)}" loading="lazy">

</td>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(n\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e28f21ea5b5690e06e43c6cb237bd0709dd36cd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.399ex; height:2.843ex;" alt="{\displaystyle \Theta \left(n\right)}" loading="lazy">

</td></tr>

<tr>

<td><a href="Knuth-Morris-Pratt-Algorithmus" title="Knuth-Morris-Pratt-Algorithmus">Knuth-Morris-Pratt-Algorithmus</a>

</td>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(m\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c1fac36dd016e3eb6bb57f00fae9a08a7a55d9bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.045ex; height:2.843ex;" alt="{\displaystyle \Theta \left(m\right)}" loading="lazy">

</td>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(n\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e28f21ea5b5690e06e43c6cb237bd0709dd36cd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.399ex; height:2.843ex;" alt="{\displaystyle \Theta \left(n\right)}" loading="lazy">

</td></tr>

<tr>

<td><a href="Boyer-Moore-Algorithmus" title="Boyer-Moore-Algorithmus">Boyer-Moore-Algorithmus</a><a href="#cite_note-2">[2]</a>

</td>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(m\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c1fac36dd016e3eb6bb57f00fae9a08a7a55d9bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.045ex; height:2.843ex;" alt="{\displaystyle \Theta \left(m\right)}" loading="lazy">

</td>

<td>average <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta \left(n/m\right)}">

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(n/m\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/844a173e2d251d6a6ec94db577d3009a8fccdf78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.602ex; height:2.843ex;" alt="{\displaystyle \Theta \left(n/m\right)}" loading="lazy">, worst <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta \left(n\cdot m\right)}">

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(n\cdot m\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fdc704d9de72c93d5e78ae9b401b1e3a93152147.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.119ex; height:2.843ex;" alt="{\displaystyle \Theta \left(n\cdot m\right)}" loading="lazy">

</td></tr>

<tr>

<td><a href="Shift-Or-Algorithmus" class="mw-redirect" title="Shift-Or-Algorithmus">Shift-Or-Algorithmus</a>

</td>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(m+|\Sigma |\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/14516385de3512575ce6b20cee927d11c41e8e19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.857ex; height:2.843ex;" alt="{\displaystyle \Theta \left(m+|\Sigma |\right)}" loading="lazy">

</td>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(n\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e28f21ea5b5690e06e43c6cb237bd0709dd36cd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.399ex; height:2.843ex;" alt="{\displaystyle \Theta \left(n\right)}" loading="lazy">

</td></tr>

<tr>

<td>Suche im <a href="Suffixbaum" title="Suffixbaum">Suffixbaum</a>

</td>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(n\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e28f21ea5b5690e06e43c6cb237bd0709dd36cd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.399ex; height:2.843ex;" alt="{\displaystyle \Theta \left(n\right)}" loading="lazy">

</td>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(m\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c1fac36dd016e3eb6bb57f00fae9a08a7a55d9bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.045ex; height:2.843ex;" alt="{\displaystyle \Theta \left(m\right)}" loading="lazy">

</td></tr></tbody></table>

Wobei m die Länge der Suchmaske und n die Länge des Textes ist.

<div class="mw-heading mw-heading3"><h3 id="Weitere_Algorithmen">Weitere Algorithmen</h3></div>

<ul><li>Skip-Search-Algorithmus</li>

<li><a href="Baeza-Yates-Gonnet-Algorithmus" title="Baeza-Yates-Gonnet-Algorithmus">Baeza-Yates-Gonnet-Algorithmus</a> (Shift-Or oder Shift-And)</li>

<li>BNDM (Backward Nondeterministic Dawg Matching)</li>

<li>BOM (Backward Oracle Matching)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Multi-String-Matching">Multi-String-Matching</h2></div>

Die Suche nach mehreren Mustern in einem Text nennt sich Multi-String-Matching<a href="#cite_note-3">[3]</a>. Die meisten Algorithmen sind abgeleitet von einem entsprechenden String-Matching Algorithmus für genau ein Muster. Eine besondere Herausforderung bei der Suche nach mehreren Suchwörtern ist die Behandlungen von Wort-Überlappungen.

<div class="mw-heading mw-heading3"><h3 id="Liste_von_Algorithmen">Liste von Algorithmen</h3></div>

<th>Multi-String-Algorithmus</th>

<th>passender Single-String-Algorithmus

</th></tr>

<tr>

<td>Multi-Shift-And</td>

<td>Shift-And

</td></tr>

<tr>

<td><a href="Aho-Corasick-Algorithmus" title="Aho-Corasick-Algorithmus">Aho-Corasick</a></td>

<td>Knuth-Morris-Pratt

</td></tr>

<tr>

<td>Commentz-Walter</td>

<td>Boyer-Moore

</td></tr>

<tr>

<td>Set-Horspool</td>

<td>Horspool

</td></tr>

<tr>

<td>Wu-Manber</td>

<td>Horspool/Rabin-Karp

</td></tr>

<tr>

<td>BOM

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Mustervergleichssuche">Mustervergleichssuche</h2></div>

<div class="hauptartikel" role="navigation">→ Hauptartikel: <a href="Pattern_Matching" title="Pattern Matching">Pattern Matching</a></div>

Die Suche nach Mustern ist zwischen unscharfer und exakter Suche anzusiedeln, da der Benutzer explizit angeben muss, welchen Spielraum er für bestimmte Zeichenklassen an bestimmten String-Positionen zulässt.

<div class="mw-heading mw-heading2"><h2 id="Unscharfe_Suche">Unscharfe Suche</h2></div>

<div class="hauptartikel" role="navigation">→ Hauptartikel: <a href="Unscharfe_Suche" title="Unscharfe Suche">unscharfe Suche</a> und <a href="Phonetische_Suche" title="Phonetische Suche">phonetische Suche</a></div>

Bei der unscharfen Suche entscheidet üblicherweise der Algorithmus nach Vorgabe eines Güte- oder Abstandskriteriums, wie groß die Abweichung von Treffern gehen darf.

Diese Form der Suche umfasst auch Suchen nach gleichlautenden Wörtern in einem Text (phonetische Suche). Beispiele von Algorithmen sind:

<ul><li><a href="Soundex" title="Soundex">Soundex</a></li>

<li><a href="K%C3%B6lner_Phonetik" title="Kölner Phonetik">Kölner Phonetik</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Suchverfahren" title="Suchverfahren">Suchverfahren</a></li>

<li><a href="Levenshtein-Distanz" title="Levenshtein-Distanz">Levenshtein-Distanz</a> (approximative Suche)</li>

<li><a href="Gestalt_Pattern_Matching" title="Gestalt Pattern Matching">Gestalt Pattern Matching</a> (approximative Suche)</li>

<li><a href="Volltextrecherche" title="Volltextrecherche">Volltextrecherche</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www-igm.univ-mlv.fr/~lecroq/string/">Java-Animationen, die die Funktionsweise so gut wie aller exakten Suchalgorithmen veranschaulichen</a></li>

<li><a rel="nofollow" class="external text" href="http://johannburkard.de/software/stringsearch/">StringSearch – high-performance pattern matching algorithms in Java</a> – Implementierungen vieler String-Matching-Algorithmen in Java (BNDM, Boyer-Moore-Horspool, Boyer-Moore-Horspool-Raita, Shift-Or)</li>

<li><a rel="nofollow" class="external text" href="http://stringsandchars.amygdalum.net/">StringsAndChars</a> – Implementierungen von String-Matching-Algorithmen für ein und mehrere Muster in Java.</li>

<li><a rel="nofollow" class="external text" href="http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bm.htm">einfache und ausführliche Erklärung des Boyer-Moore-Algorithmus</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> Dan Gusfield: <cite style="font-style:italic">Algorithms on Strings, Sequences and Trees</cite>. 1997, ISBN 0-521-58519-8, Kapitel 7.1.APL1 (1999 korrigierte Ausgabe).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abookitem&rfr_id=info:sid/de.wikipedia.org:String-Matching-Algorithmus&rft.atitle=Kapitel+7.1.APL1&rft.au=Dan+Gusfield&rft.btitle=Algorithms+on+Strings%2C+Sequences+and+Trees&rft.date=1997&rft.genre=bookitem&rft.isbn=0521585198" style="display:none">

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> R. S. Boyer, J. S. Moore: <cite style="font-style:italic">A fast string searching algorithm</cite>. In: <cite style="font-style:italic"><a href="Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a></cite>. 20. Jahrgang, 1977, S. 762–772, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145/359842.359859">10.1145/359842.359859</a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:String-Matching-Algorithmus&rft.atitle=A+fast+string+searching+algorithm&rft.au=R.+S.+Boyer%2C%26%2332%3BJ.+S.+Moore&rft.btitle=Communications+of+the+ACM&rft.date=1977&rft.doi=10.1145%2F359842.359859&rft.genre=book&rft.pages=762-772&rft.volume=20.+Jahrgang" style="display:none">

</li>

<li id="cite_note-3"><a href="#cite_ref-3">↑</a> Gonzalo Navarro, Mathieu Raffinot: <cite style="font-style:italic">Flexible Pattern Matching Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences</cite>. 2008, ISBN 0-521-03993-2.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:String-Matching-Algorithmus&rft.au=Gonzalo+Navarro%2C+Mathieu+Raffinot&rft.btitle=Flexible+Pattern+Matching+Strings%3A+Practical+On-Line+Search+Algorithms+for+Texts+and+Biological+Sequences&rft.date=2008&rft.genre=book&rft.isbn=0521039932" style="display:none">

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2022-10-29" href="https://de.wikipedia.org/wiki/?title=String-Matching-Algorithmus&oldid=227452349">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>